Metode numerice - Aplicatii

Lucrarea 2.   Criteriul de aproximare prin interpolare: polinoame Newton si Lagrange.

Tema A - Polinoame Newton cu diferente divizate            Tema B - Polinoame Lagrange

    Formularea cea mai generala a problemei de aproximare cere ca, pornind de la o functie f(x) definita pe un anumit domeniu, sa se determine o alta functie F(x), avand o forma cat mai simpla, care sa aproximeze cat mai bine functia f(x) pe intregul domeniu de definitie. Evident, o data aproximatia F(x) stabilita, ea va inlocui functia originara f(x) in toate calculele ulterioare.
    Cel mai frecvent, problemele de aproximare apar in cazul unor functii definite tabelar. Functia f(x) este descrisa de un set de "puncte" definite de perechi de forma (valoare variabila - valoare functie). Despre o asemenea functie se spune ca este definita sub forma tabelara, conform urmatorului model:
 

x_k x_1 x_2 ... x_i ... x_(n+1)
f(x_k) f_1 f_2 ... f_i ... f_(n+1)

    Tabelul de definitie contine n+1 puncte (x_k , f_k), pentru care f_k = f (x_k). In multe situatii practice nu se urmareste determinarea explicita a unei expresii pentru functia de aproximare F(x), ci numai a valorii sale intr-un punct oarecare x. Daca acest punct se gaseste in interiorul domeniului de definitie al functiei f(x), se vorbeste de interpolare, iar daca se afla in afara domeniului de definitie, se vorbeste de extrapolare. Punctele x_k in care este cunoscuta functia f(x) se numesc noduri de interpolare, iar multimea lor (x_1 , x_2 , ... , x_n) formeaza suportul de interpolare.

Tema A - Polinoame Newton cu diferente divizate

    Polinomul de interpolare Newton de grad n cu diferente divizate, notat N_n(x), se exprima in functie de distantele dintre punctul de calcul x si nodurile de interpolare. Se poate folosi polinomul de interpolare Newton de speta intai:

sau polinomul de interpolare Newton de speta a doua:

    Interpolarea folosind polinomul Newton de speta intai este eficienta mai ales pentru puncte de interpolare/extrapolare situate catre inceputul, respectiv  la  stanga  intervalului  de  definitie [x_1 , x_(n+1)].  Pentru   puncte   de   calcul   situate  la  extremitatea  opusa  a  intervalului  [x_1 , x_(n+1)] se recomanda folosirea polinomului Newton de speta a doua.

    In expresiile polinoamelor Newton marimile notate cu se numesc diferente divizate de un anumit ordin si definite in raport cu un anumit nod de interpolare. Diferentele divizate se pot construi pornind de la urmatoarea structura tabelara (in continuare ne vom referi numai la polinomul Newton de speta intai):

si relatia de recurenta:

unde j indica ordinul diferentei, iar i nodul de interpolare de la care incolo se defineste diferenta divizata. Astfel, diferenta divizata  este definita intre nodurile de interpolare x_i si x_(i+1). Se mentioneaza ca diferentele divizate de ordin 1 sunt egale cu valorile functiei de aproximat in nodurile respective:

Pentru memorarea diferentelor divizate care intervin in expresia polinomului Newton se poate folosi un singur vector D, dupa urmatoarea schema:

Initial, vectorul D contine valorile functiei in nodurile de interpolare, identice cu diferentele divizate de ordin unu. Se calculeaza succesiv diferentele divizate de ordin crescator in raport cu primul nod de interpolare. In vectorul D, calculul diferentelor divizate se face de jos în sus.


Algoritmul 1 - Interpolarea cu polinoame Newton de grad impus
  1. Definirea functiei tabelare: gradul polinomului de interpolare n, valorile nodurilor de interpolare x_k si ale functiei aproximate f_k(k=1,..., n+1).
  2. Initializarea vectorului diferentelor divizate: , k=1,...,n+1
  3. Calculul diferentelor divizate de ordin 1,2,...,n in raport cu primul nod de interpolare:
  4. Aproximarea functiei originare:
    1. Introducerea punctului de aproximare x*.
    2. Calculul valorii aproximative:
    3. Confirmarea aproximarii intr-un nou punct si revenirea la pasul 4.i. In caz contrar se intrerupe algoritmul.

Folosind acest algoritm functia este aproximata cu un polinom de grad fix, a carui valoare este impusa de numarul nodurilor de interpolare folosite (n-1). Daca tabelul de definitie al functiei f(x) contine un numar mare de noduri de interpolare, rezulta un polinom de grad mare, ceea ce genereaza riscul aparitiei unor oscilatii puternice intre nodurile de interpolare. Pentru a evita aceste oscilatii se poate folosi interpolarea cu polinoame Newton de grad liber. In acest caz, pentru un punct de calcul x* se folosesc numai cateva noduri din tabelul de definitie a functiei f(x), si anume nodurile cele mai apropiate de punctul de calcul x*.


Algoritmul 2 - Interpolarea cu polinoame Newton de grad liber
  1. Definirea functiei tabelare: gradul maxim al polinomului de interpolare n, valorile nodurilor de interpolare x_k si ale functiei aproximate f_k(k=1,...,n+1).
  2. Definirea punctului de interpolare x* si a preciziei de calcul EF.
  3. Ordonarea nodurilor de interpolare in raport cu punctul de calcul. Vectorul IX_i (i=1,...,n+1) contine indecsii nodurilor de interpolare ordonati crescator.
  4. Initializarea procesului de aproximare:
    • formarea vectorului diferentelor divizate:
      (i=1,...,n+1);
    • gradul polinomului: Gr <-- 0 ;
    • polinomul:
    • criteriul de oprire:
  5. Procesul de aproximare:
    1. Daca s-a atins gradul maxim (Gr=n) sau s-a atins precizia de calcul (DF<EF) se trece la pasul 6;
    2. Incrementarea gradului polinom:Gr <-- Gr + 1;
    3. Calculul diferentei divizate de ordin Gr :
         k=n+1,...,Gr+1;
    4. Calculul noii aproximatii:
    5. Criteriul de oprire:
    6. Se revine la pasul 5.i;
  6. Afisarea valorii aproximative F_x si a gradului polinomului de interpolare Gr

Tema B - Polinoame Lagrange

    Pornind de la  functia f(x) definita tabelar, polinomul de interpolare Lagrange de grad n, notat L_n(x) se defineste ca o combinatie liniara de polinoame  k=1,...,n+1, care formeaza baza de interpolare. Coeficientii combinatiei liniare sunt tocmai valorile functiei de aproximat in nodurile de interpolare:

Expresiile polinoamelor  se detremina impunand conditia ca polinomul Lagrange astfel definit sa satisfaca conditiile de interpolare. In final, pentru polinomul L_n(x) se obtine expresia:
Si in acest caz polinomul de aproximare calculat cu expresia de mai sus are gradul impus de numarul nodurilor de interpolare care apar in tabelul de definitie al functiei de aproximat.


Algoritmul 3 - Interpolarea cu polinoame Lagrange de grad impus
  1. Definirea functiei tabelare: gradul polinomului de interpolare n, valorile nodurilor de interpolare x_k si ale functiei aproximate f_k(k=1,..., n+1).
  2. Aproximarea functiei originare:
    1. Introducerea punctului de aproximare x*.
    2. Calculul valorii aproximative:
    3. Confirmarea aproximarii intr-un nou punct si revenirea la pasul 2.i. In caz contrar se intrerupe algoritmul.

Pentru a evita aparitia oscilatiilor intre nodurile de interpolare - oscilatii care apar in special in cazul unui numar mare de noduri de interpolare - se poate folosi interpolarea cu polinoame Lagrange de grad liber. Pentru un punct de calcul x* se folosesc numai o parte din nodurile din tabelul de definitie a functiei f(x), si anume nodurile cele mai apropiate de punctul de calcul x*.

Polinomului de interpolare Lagrange i se poate asocia un tablou asemanator celui al diferentelor divizate (vezi polinomul de interpolare Newton), format insa din polinoame Lagrange calculate pe o multime de noduri de interpolare diferite de la un element la altul. In continuare se folosesc notatiile:

  • L_1,n-1(x) - polinomul Lagrange de grad n-1 care trece prin primele n noduri de interpolare (x_1 , f_1), (x_2 , f_2), ... , (x_n , f_n)
  • L_2,n-1(x) - polinomul Lagrange de grad n-1 care trece prin ultimele n noduri de interpolare (x_2 , f_2), (x_3 , f_3), ... , (x_n+1 , f_n+1)
  • L_1,n(x) - polinomul Lagrange de grad n care trece prin toate cele n+1 noduri de interpolare.

Intre aceste polinoame exista relatia:

In general, se poate defini un polinom Lagrange generic L_i,j (x) de grad j care trece prin j+1 noduri de interpolare, incepand cu nodul i, adica prin punctele (x_i , f_i), (x_i+1 , f_i+1), ... , (x_i+j , f_i+j):
Exista un singur polinom de grad n (L_1,n (x)), doua polinoame de grad n-1 (L_1,n-1 (x) si L_2,n-1 (x)) s.a.m.d. pana la n+1 polinoame de grad 0 (L_1,0 (x), L_2,0 (x), ... , L_n+1,0 (x)) identice cu valorile functiei in nodurile de interpolare. Aceste polinoame pot fi organizate intr-un tablou de forma:

Dintre polinoamele L_i,j din acest tablou, cele care intereseaza sunt cele care folosesc succesiv 1, 2, ... , n+1 noduri de interpolare. Aceste polinoame sunt L_1,1 , L_1,2 , ... , L_1,n+1, adica prima linie din tabloul de mai sus. Pentru a putea calcula insa polinomul L_1,n+1 este necesar calculul in prealabil al tuturor celorlalte polinoame din tablou.

Se constata existenta unei similitudini formale cu polinoamele Newton care folosesc diferente divizate. Si in acest caz este necesara renumerotarea nodurilor de interpolare in raport cu punctul de calcul x*. De asemenea, valorile polinoamelor L_i,j pot fi memorate intr-un singur vector, dupa un model asemanator celui prezentat in cazul polinoamelor Newton.


Algoritmul 4 - Interpolarea cu polinoame Lagrange de grad liber
  1. Definirea functiei tabelare: gradul polinomului de interpolare n, valorile nodurilor interpolare x_k si ale functiei aproximate f_k(k=1,..., n+1).
  2. Definirea punctului de interpolare x* si a preciziei de calcul EF.
  3. Ordonarea nodurilor de interpolare in raport cu punctul de calcul. Vectorul IX_i (i=1,...,n+1) contine indecsii nodurilor de interpolare ordonati crescator.
  4. Initializarea procesului de aproximare:
    • formarea vectorului polinoamelor Lagrange partiale :
      (i=1,...,n+1);
    • gradul polinomului: Gr <-- 0 ;
    • aproximatia initiala :
    • criteriul de oprire:
  5. Procesul de aproximare:
    1. Daca s-a atins gradul maxim (Gr=n)sau s-a atins precizia de calcul (DF<EF) se trece la pasul 6;
    2. Incrementarea gradului polinom: Gr <-- Gr + 1;
    3. Calculul noii aproximatii:
      k=n+1, ... ,Gr+1 si memorarea noii aproximatii : F_x <-- d_(Gr+1);
    4. Criteriul de oprire:
    5. Se revine la pasul 5.i;
  6. Afisarea valorii aproximative F_x si a gradului polinomului de interpolare Gr.

Pentru alte variante de implementare a modelului de aproximare cu polinoame Lagrange, se poate consulta cartea "Calcul numeric cu aplicatii in Turbo Pascal".
 

   Aplicatii - Lista lucrarilor de laborator